package leetcode.editor.cn;

/**
题目名字---:最大子序和
题目编号---:53	
解题时间---:2021-10-16 11:38:18
*/

public class MaximumSubarray{
    public static void main(String[] args) {
        Solution solution = new MaximumSubarray().new Solution();
        int [] arr ={-2,1,-3,4,-1,2,1,-5,4};
        solution.maxSubArray(arr);
    }

    /**
     * 暴力求解超时
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int result = nums[0];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                int temp = i;
                int tempResult =0;
                for (;temp<=j;temp++) {
                    tempResult+=nums[temp];
                }
                if (tempResult>result) {
                    result = tempResult;
                }
            }
        }
        return result;
    }
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
}
//leetcode submit region end(Prohibit modification and deletion)


}